/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/bitwise-and-of-numbers-range
   @Language: C++
   @Datetime: 20-01-06 15:51
   */

// Method 1, base idea
class Solution {
public:
	int rangeBitwiseAnd(int m, int n) {
		int res=0;
		for(int b=0; m; m>>=1, n>>=1, ++b){
			if(m<n || (m&1)==0) continue;
			res|=1<<b;
		}
		return res;
	}
};

// Method 2, common prefix
class Solution {
public:
	int rangeBitwiseAnd(int m, int n) {
		for(; n>m; n&=n-1);
		return n;
	}
};
